#include <iostream>
using namespace std;
const int MOD = 109;
int main()
{
	int n, m;
	cin >> n >> m;
	int ret = n;
	for (int i = 0; i < m - 1; i++)
	{
		ret = ret * (n - 1) % MOD;
	}

	cout << ret << endl;

	return 0;
}